<!DOCTYPE html>
<html lang="en">
  <head>
    <meta charset="UTF-8" />
    <meta name="viewport" content="width=device-width, initial-scale=1.0" />
    <title>Document</title>
  </head>
  <body>
    <script>
      /*
      每个单词可以使用多次，所以是完全背包。
      物品为wordDict，背包容量为s.length
      求物品是否可以装满背包。物品的重量为wordDict[i].length

      ①初始化dp数组  dp[i]表示当长度为i的字符串s是否能由字典表示

      ②状态转移方程： 如果dp[i]==true 且 (i,j)在字典里 那么dp[j]=true
    
      */
      var wordBreak = function (s, wordDict) {
        let bagSize = s.length
        let dp = new Array(bagSize + 1).fill(false)
        dp[0] = true
        for (let j = 0; j <= bagSize; j++) {
          for (let i = 0; i < wordDict.length; i++) {
            if (j >= wordDict[i].length) {
              //找出剩余字符判断是否符合条件
              //为什么是从j-wordDict[i].length因为我们每次裁剪出来的必须保证满足字典里字符长度
              let str = s.slice(j - wordDict[i].length, j)
              if (wordDict.includes(str) && dp[j - wordDict[i].length]) {
                dp[j] = true
              }
            }
          }
        }
        return dp[bagSize]
      }
    </script>
  </body>
</html>
